<!DOCTYPE html>
<html lang="zhcn">

<head>
  <meta charset="UTF-8">
  <meta http-equiv="X-UA-Compatible" content="IE=edge">
  <meta name="viewport" content="width=device-width, initial-scale=1.0">
  <title>Document</title>
</head>

<body>
  <script type="module">
    // 请用服务打开, 否则跨域
    import Dict from './dict.js'
    import Queue from './queue.js'

    // 封装图 (无向邻接表表示)
    function Graph (){
      // 图: 先添加顶点, 再添加两点之间的边
      this.vertexes = []
      this.edges = new Dict()

      Graph.prototype.addVertex = function(v){
        // 1. 添加顶点.
        if(!this.vertexes.includes(v)){
          this.vertexes.push(v)
          // 2. 初始化边的领接表
          this.edges.set(v,[])
        }
      }

      Graph.prototype.addEdge = function(v1,v2){
         // 1. 不允许直接添加边
         if(!this.vertexes.includes(v1) || !this.vertexes.includes(v2)){
           throw new Error('You should add the edge before added vertex')
         }
         //2. 这个是无向邻接表
         this.edges.get(v1).push(v2)  
         this.edges.get(v2).push(v1)  
      }

      // toString
      Graph.prototype.toString = function(){
        let str = ""
        this.vertexes.forEach(v => {
          // A --> 
          str += (v + ' -->')
          // A --> B C D
          this.edges.get(v).forEach(v2 => (str += ` ${v2}`))
          // 一条边完了, 换行
          str += '\n'
        })
        return str
      }

      // 每一个顶点可能有三种颜色, white, black, 灰
      // white代表顶点没有被处理过
      // black代表顶点完全处理过
      // gray 代表顶点被探索过, 但没处理过

      Graph.prototype.initColor = function(){
        // 记录每个顶点的颜色
        const vertextes = this.vertexes
        const color = []
        // 拿到每个顶点, 给顶点赋值为白色
        vertexes.forEach(v => color[v] = 'white')

        return color
      }

      // 广度优先搜索 breadthFirstSearch
      // 从哪个节点开始搜索, 处理函数
      Graph.prototype.BFS = function(startVertex,handler) {
        // 1. 初始化队列状态, 将顶点放进队列中
        const queue = new Queue()
        queue.enqueue(startVertex)
        const colors = this.initColor()
        // 2. 拿出队列中第一个元素, 将元素的兄弟放进队列中, 重复这个过程
        while(!queue.isEmpty()){
          const activeV = queue.dequeue()
          handler(activeV)
          colors[activeV] = 'black'

          const activeVSiblings =  this.edges.get(activeV)
          activeVSiblings.forEach(v =>{
            if(colors[v] === 'white' ){
              queue.enqueue(v)
              colors[v] = 'gray'
           }
          })
       }
      }

     // 拿出第一个顶点处理, 处理完当前节点处理该节点的兄弟节点
      Graph.prototype.DFS = function(firstV,handler){
        this.processV(firstV,this.initColor(),handler)
      }


      Graph.prototype.processV = function(v,colors,handler){
        colors[v] = 'gray' //访问过变成灰

        handler(v) // 处理v

        colors[v] = 'black' // 处理过变成黑

        // 处理子节点, 子节点的处理遵循先子后兄弟
        const vertexes = this.edges.get(v)
        vertexes.forEach(v => {
          if(colors[v] === 'white'){
            this.processV(v,colors,handler)
          }
        })


      }

    }

    const g = new Graph()
    const vertexes = ['A','B','C','D','E','F','G','H','I']
    vertexes.forEach(v => g.addVertex(v))
    g.addEdge('A','B')
    g.addEdge('A','C')
    g.addEdge('A','D')
    g.addEdge('C','D')
    g.addEdge('C','G')
    g.addEdge('D','G')
    g.addEdge('D','H')
    g.addEdge('B','E')
    g.addEdge('B','F')
    g.addEdge('E','I')
    console.log(g.toString());
    console.log('color',g.initColor())

    g.BFS('A',function(v){
      console.log(v)
    })

    g.DFS('A',function(v){
      console.log('深度遍历',v)
    })
  </script>
</body>

</html>